#include <string>
#include "string.h"
#include <iostream>
#include <math.h>
#include <time.h>
#include <random>
#define CITY_NUM 31
#define candidates 200
#define INF INT_MAX
using namespace std;


double city[31][2]={
        {1304,2312},{3639,1315},{4177,2244},{3712,1399},{3488,1535},{3326,1556},{3238,1229},
        {4196,1044},{4312,790},{4386,570},{3007,1970},{2562,1756},{2788,1491},{2381,1676},
        {1332,695},{3715,1678},{3918,2179},{4061,2370},{3780,2212},{3676,2578},{4029,2838},
        {4263,2931},{3429,1908},{3507,2376},{3394,2643},{3437,3201},{2935,3240},{3140,3550},
        {2545,2357},{2778,2826},{2370,2975}
};

double disList[CITY_NUM][CITY_NUM];
double tabuList[CITY_NUM][CITY_NUM];
int tabuLength=sqrt(CITY_NUM*(CITY_NUM-1)/2);
int candidateNum[candidates][CITY_NUM];
double bestL;

void CreateRandOrder(int* city, const int & N){
    for (int i = 0; i < N; i++){
        city[i] = rand() % N;
        for (int j = 0; j < i; j++){
            if (city[i] == city[j]){
                i--;
                break;
            }
        }
    }
}

double GetPathLen(double disList[CITY_NUM][CITY_NUM], int*city){
    double res = 0;
    int i;
    for (i = 0; i < CITY_NUM-1; i++){
        res+=disList[city[i]][city[i+1]];
    }
    return res;
}

int main(){
//    while(i<CITY_NUM){
//        cout<<city[i][0]<<","<<city[i][1]<<endl;
//        i++;
//    }
    for(short i=0;i<CITY_NUM;i++){
        for(short j=0;j<CITY_NUM;j++){
            disList[i][j]=sqrt(pow(city[i][0]-city[j][0],2)+pow(city[i][1]-city[j][1],2));
//            cout<<tabuList[i][j]<<",";
        }
//        cout<<endl;
    }
    memset(tabuList,0, sizeof(tabuList));
    memset(candidateNum,0, sizeof(candidateNum));
    int S0[31];
    CreateRandOrder(S0,CITY_NUM);
//    for (int i = 0; i < CITY_NUM; i++){
//        cout<<S0[i]<<",";
//    }
    bestL=INF;
    int p=1,stopL=2000;
//    cout<<GetPathLen(disList,S0);

    while(p<stopL){
//        if(candidates>CITY_NUM*(CITY_NUM-1)/2){
//            cout<<"候选解个数不大于n*(n-1)/2!"<<endl;
//            break;
//        }
        double dis0=GetPathLen(disList,S0);
        int i=0;
        int A[candidates][2];
        int isa;
        while(i<candidates){
            int M[2];
            default_random_engine e(time(0));
            uniform_real_distribution<double> u(0,1);
            M[0]=CITY_NUM*u(e);M[0]++;
            M[1]=CITY_NUM*u(e);M[1]++;
            cout<<M[0]<<","<<M[1]<<endl;
            if(M[0]!=M[1]){
                A[i][0]=max(M[0],M[1]);
                A[i][1]=min(M[0],M[1]);
                if(i==0){
                    isa=0;
                }else {
                    for(short j=0;j<i-1;j++){
                        if(A[i][0]==A[j][0]&&A[i][1]==A[j][1]){
                            isa=1;
                            break;
                        }else {
                            isa=0;
                        }
                    }
                }
                if(!isa){
                    i++;
                }

            }
        }

        int BestCandidateNum=100;
        double

        for()

        p++;
    }

    return 0;
}